Consumer products, business products and even military equipment become more dependent on computer systems with each passing day. When products incorporate computing equipment, people may try to take advantage of product weaknesses, either to use the product for free or to sabotage the product. In the computing world, hackers, pirates or adversaries may try to take advantage of products that use computing equipment by tampering with the memory of the equipment. Typically there are two main areas of security when it comes to protecting computing integrity: software based and hardware based. Software based security is concerned with the integrity of software. Hardware based security assumes that a hacker has full access to a computing system and may use oscilloscopes and logic analyzers to observe the computing system.
Advances in very large scale integration of circuits on a chip have provided tamper resistant hardware computing systems by integrating complete Systems on a Chip (SoC). Thus integrating the whole computing system onto a chip may stop an adversarial attack. In most practical scenarios, however, insufficient on-chip memory renders this solution unattainable. Programs and data must be stored in off-chip memory. This opens an avenue for an adversary to compromise computing equipment by tampering with off-chip memory.
Signing and encrypting memory is a way to stop an adversary from successfully tampering with off-chip memory. A message signature is like a checksum that may be used to verify that a piece of memory has not changed since it was last read. When data is written to off-chip memory, a signature is generated and stored with the data. When the data is read from off-chip memory, the signature is verified to ensure that data has not changed. Generating a signature can be an expensive operation. Many clock cycles may be used to generate a signature. Thus, generating and checking a memory signature must be efficient.
Message authentication has been a subject of a large amount of research. While most natural MAC schemes involve simple evaluation of a pseudorandom permutation (PRP) on the message concatenated with redundant data (such as a string of 32 zeros), such schemes do not lend themselves to pre-computation.
Another approach to MAC computation uses universal hash functions (UHF). The idea to obtain a MAC from a UHF was first proposed by Carter and Wegman (Wegman, Carter, New Hash Functions and Their Use in Authentication and Set Equality, JCSS, 22:265, 1981). Brassard later proposed to use pseudorandom generators to reduce the size of MAC keys (Gilles Brassard, On computationally secure authentication tags requiring short secret shared keys, in Crypto'82, 79-86.) The resulting construction is as follows: MAC (m,r)=h(m) XOR F(r), where h is a UHF and F is a pseudorandom generator. Since then, a substantial amount of research concentrated on speed and other improvements of the used functions h and F.
The MAC pre-computation construction differs from previously proposed constructions, and possesses properties specifically desired in short message authentication with pre-computation.